import java.io.*;
import java.util.*;
import java.lang.Float;
import java.math.*;
class Meul {
	public static int numberOfBuckets;
	public static BucketArray P;
	public static BucketArray N;
	public static int flops;
	public static float[] inputArray;
	public static class UnrolledLinkedList {
		Node lastNode;
		// length of the unrolledLinkedList
		int length;
		// constant size of each array in each node
		int maxElementsInArray;
		public UnrolledLinkedList(int maxElementsInArray) {
			this.maxElementsInArray = maxElementsInArray;
			lastNode = new Node(new Node(null));
			length = 0;
		}

		public void addToEnd(float f) {
			if(lastNode.numberOfElementsInArray == maxElementsInArray)
				lastNode = new Node(lastNode);
			lastNode.array[lastNode.numberOfElementsInArray] = f;
			lastNode.numberOfElementsInArray++;
			length++;
		}

		public float removeFromEnd() {
			length--;
			lastNode.numberOfElementsInArray--;
			float returnValue = lastNode.array[lastNode.numberOfElementsInArray];
			if(lastNode.numberOfElementsInArray == 0 && lastNode.previousNode != null) 
				lastNode = lastNode.previousNode;
			return returnValue;
		}

		class Node {
			public float[] array;
			public int numberOfElementsInArray;
			public Node previousNode;
			public Node(Node previousNode) {
				array = new float[maxElementsInArray];
				this.previousNode = previousNode;
				numberOfElementsInArray = 0;
			}
		}
	}

	public static class BucketArray {
		UnrolledLinkedList[] buckets;
		int count;
		
		public BucketArray(int numberOfBuckets) {
		        buckets = new UnrolledLinkedList[numberOfBuckets];
			for(int i = 0; i < buckets.length; i++) {
				buckets[i] = new UnrolledLinkedList(5000);
			}
			count = 0;
		}

		public float removeLastFloatFromBucket(int bucketNumber) {
			return buckets[bucketNumber].removeFromEnd();
		}
		
		public void insert(float f) {
			if(f != 0 && f != -0) {
				int e = ((Float.floatToIntBits(f)) & 0x7f800000) >> 23;// - 127;
				if(e == 0) {
					System.out.println("count " + count);
					count++;
				}
				buckets[e].addToEnd(f);
			}
		}
	}

	public static class SumAndError {
		float s;
		float e;
		public SumAndError(float s, float e) {
			this.s = s;
			this.e = e;
		}
	}

	public static void main(String args[]) {
		numberOfBuckets = 255;
		N = new BucketArray(numberOfBuckets);
		P = new BucketArray(numberOfBuckets);
		flops = 0;

		// load data from a file
		long loadStart = System.currentTimeMillis();
		loadNumbersFromAFile();	
		long loadEnd = System.currentTimeMillis();
		System.out.println("time to load data " + (loadEnd - loadStart));
	
	         // bucket sort the data	
		 long sortStart = System.currentTimeMillis();
		 fillBucketsWithNumbers();
		 long sortEnd = System.currentTimeMillis();
		 long sortTime = sortEnd - sortStart;
		 System.out.println("time to bucketSort " + sortTime); 

		// run the algorithm
		// the 254th bucket is the top most bucket
		// the 255th bucket is never used, its reserved for 
		// infinity and not a number
		long startTime = System.currentTimeMillis();
		// while one of the last buckets is not empty 
		while(someBucketsHaveMoreNumbers()) {
			// for the first bucket
			moveNumbersUp(0);
			// for each bucket except the first and the last bucket
			for(int i = 1; i < numberOfBuckets - 1; i++) {
				moveNumbersDown(i);
				moveNumbersUp(i);
			}
			// for the last bucket
			moveNumbersDown(numberOfBuckets - 1);
		}
		float sum = topDownCompensatedSummation();
		long endTime = System.currentTimeMillis();
		long runTime = endTime - startTime;

		System.out.println("time to run " + (endTime - startTime));
		System.out.println("total time " + (sortTime + runTime));

		if(Float.isNaN(sum) || Float.isInfinite(sum)) {
			System.out.println("overflow");
		}
		else {
			System.out.println(new BigDecimal(sum));
			System.out.println("flops " + flops);
		}
	}

	static boolean someBucketsHaveMoreNumbers() {
		// for each bucket except the  first and the last
		for(int i = 1; i < numberOfBuckets - 1; i++) {
			if((P.buckets[i].length > 1 || N.buckets[i].length > 1) || 
			   (P.buckets[i].length == 1 && N.buckets[i].length == 1)) {
				return true;
			}
		}
		// for the frist bucket
		if(P.buckets[0].length > 1 || N.buckets[0].length > 1)
			return true;
		//  for the last bucket
		if(P.buckets[numberOfBuckets - 1].length > 0 && N.buckets[numberOfBuckets - 1].length > 0)
			return true;
		return false;
	}

	static float topDownCompensatedSummation() {
		Stack whatsLeft = new Stack();
		for(int i = numberOfBuckets - 1; i >= 0; i--) {
			while(P.buckets[i].length > 0) {
				float temp = P.removeLastFloatFromBucket(i);
				whatsLeft.push(temp);
			System.out.println(" i " + i + " " + temp);
			}
			while(N.buckets[i].length > 0) {
				float temp = N.removeLastFloatFromBucket(i);
				whatsLeft.push(temp);
			System.out.println(" i " + i + " " + temp);
			}
		}
		// compensated sum
		float c = 0;
		float sum = ((Float)whatsLeft.elementAt(0));
		float y = 0;
		float t = 0;
		int n = whatsLeft.size();
		for(int i = 1; i < n; i++) {
			y = ((Float) whatsLeft.elementAt(i)).floatValue() - c;
			t = sum + y;
			c = (t - sum) - y;
			sum = t;
			flops += 3;
		}
		return sum;
	}

	static void moveNumbersUp(int bucketNumber) {
		// only one of these while loops will actualy run
		// if at all
		while(P.buckets[bucketNumber].length > 1) {
			SumAndError d = exactAdd(P.removeLastFloatFromBucket(bucketNumber),
					         P.removeLastFloatFromBucket(bucketNumber));
			P.insert(d.e);
			P.insert(d.s);
		}
		while(N.buckets[bucketNumber].length > 1) {
			SumAndError d = exactAdd(N.removeLastFloatFromBucket(bucketNumber),
				                 N.removeLastFloatFromBucket(bucketNumber));
			N.insert(d.e);
			N.insert(d.s);	
		}
	}

	static void moveNumbersDown(int bucketNumber) {
		float sum;
		while(P.buckets[bucketNumber].length > 0 && N.buckets[bucketNumber].length > 0) {
			sum = 0;
			sum += P.removeLastFloatFromBucket(bucketNumber) + 
			       N.removeLastFloatFromBucket(bucketNumber); 
			flops += 2;
			if(sum < 0)
				N.insert(sum);
			else
				P.insert(sum);
		}
	}

	static SumAndError exactAdd(float a, float b) {
		flops += 3;
		float s = a + b;
		// e could be -0
		float e = -1 * ((s - a) - b);
		return new SumAndError(s, e);
	}

	public static void fillBucketsWithNumbers() {
		for(int i = 0; i < inputArray.length; i++) {
			if(inputArray[i] > 0) {
				P.insert(inputArray[i]);
			}
			if(inputArray[i] < 0) {
				N.insert(inputArray[i]);
			}
		}
	}
	
	public static void loadNumbersFromAFile() {
		Stack inputStack = new Stack();
		try {
			Scanner sc = new Scanner(new File("numbers"));
			while(sc.hasNextFloat()) {
				float temp = sc.nextFloat();
					inputStack.push(temp);
			}
			int i = 0;
			inputArray = new float[inputStack.size()];
			while(inputStack.size() > 0) {
				inputArray[i] = ((Float) inputStack.pop()).floatValue();
				i++;
			}
		}
		catch(FileNotFoundException e) {

		}	
	}
}
